package leetcode.pre100;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 示例 1:
 * <p>
 * 输入:
 * matrix = [
 * [1,   3,  5,  7],
 * [10, 11, 16, 20],
 * [23, 30, 34, 50]
 * ]
 * target = 3
 * 输出: true
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @date 2020/6/7 22:11
 */
public class Code74_SearchMatrix_搜索值 {
    /**
     * 行和列都是从小到大。从左下角或右上角入手
     */
    public static boolean isExist(int [][]m,int target){
        if(m == null || m.length == 0 || m[0].length == 0)return false;
        int row = m.length -1;
        int col = m[0].length - 1;
        int curRow = 0;
        int curCol = col;
        while (curRow <= row && curCol >=0){
            if(target < m[curRow][curCol]){
                curCol --;
            }else if(target > m[curRow][curCol]){
                curRow ++;
            }else {
                return true;
            }
        }
        return false;

    }
    /**
     * 行和列都是从大到小，也是从左下角或右上角入手
     */
    public static boolean isExist1(int [][]m,int target){
        int row = m.length -1;
        int col = m[0].length - 1;
        int curRow = 0;
        int curCol = col;
        while (curRow <= row && curCol >=0){
            if(target > m[curRow][curCol]){
                curCol --;
            }else if(target < m[curRow][curCol]){
                curRow ++;
            }else {
                return true;
            }
        }
        return false;
    }
}
